Leetcode 765.Couples Holding Hands 题解

题目链接

Leetcode 765.Couples Holding Hands

题目内容

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example1: Input: row = [0, 2, 1, 3] Output: 1 Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example2: Input: row = [3, 2, 0, 1] Output: 0 Explanation: All couples are already seated side by side.

Note: 1. len(row) is even and in the range of [4, 60]. 2. row is guaranteed to be a permutation of 0...len(row)-1.

解题思路

首先，看完题目，我就在想如何确认交换数目最小，因为经过自己比划了几个样例，思考了一下，发现由于每个错位的people都需要一次交换，所以, n对错位的Couples需要的交换次数至少为(int)((n+1)/2), 其最少次数的交换也就是从左往右交换依次错位的people，没有更少次数的移动方法。这道题目较水，只要理解了为什么从左往右遍历次数最少就很快就完成了。

所以这题就变成了如何快速找到对应的pos进行交换，因为row中的值就是在0-size的范围内，所以这里我直接用了一个indecies Vector去存储各个people对应的index，通过维护indecies[x]表示x的index来实现pos的快速查找，使得整体的时间复杂度达到O(n),这应该是这道题最快的方法，提交的Detail如下:

题目代码

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int size = row.size();
        int ans = 0;
        if (size == 2)
            return 0;
        vector<int> indecies(size, 0); // indecies[x] 为x对应的index
        for(int i = 0; i < size; i++)
            indecies[row[i]] = i;
        for (int i = 0; i < size; i += 2) {
            int trueVal = (row[i]%2 == 0) ? row[i]+1 : row[i] - 1;
            if (row[i+1] != trueVal) {
                ++ans;
                row[indecies[trueVal]] = row[i+1]; // 交换成员
                indecies[row[i+1]] = indecies[trueVal]; // 更新Pos
                row[i+1] = trueVal; // 交换成员
                indecies[row[i+1]] = i+1; // 更新Pos
            }
        }
        return ans;
    }
};